package leetcode.dp;

import java.util.Scanner;
/**
 * leetCode 5
 * 回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串
 * 思路：状态方程 P(i,j)=(P(i+1,j−1) and Si==Sj)

 */
public class Dp5 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        //利用hasNextXXX()判断是否还有下一输入项
        while (sc.hasNext()) {
            //利用nextXXX()方法输出内容
            String str = sc.next();
            new Dp5().longestPalindrome(str);
        }
    }
    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;
        boolean [][] dp = new boolean[s.length()][s.length()];
        // 子串长度为1和为2的初始化
        for(int i = 0; i < s.length(); i++){
            dp[i][i] = true;
            if(i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)){
                dp[i][i + 1] = true;
            }
        }
        for(int i = s.length() - 3; i >= 0; i--){
            for(int j = s.length() - 1 ;j > i;j --){
                if(j - i < 2) continue;
                dp[i][j] = dp[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
            }
        }
        int max = 0;
        String res = s.substring(0, 1);
        for(int i = 0; i < s.length(); i++){
            for(int j = 0;j < s.length();j ++){
                if(dp[i][j] && max < (j - i)) {
                   res = s.substring(i, j + 1);
                   max = j - i;
                }
            }
        }
        return res;
    }
}
